Network traffic often contains a significant amount of redundant data. To improve data transmission over a network, data is often compressed using data redundancy elimination (DRE) schemes. Before transmitting data, a DRE node typically divides data blocks into chunks, performs a lookup in its storage to identify chunk signatures that correspond to the chunks, and replaces redundant chunks with chunk signatures. Compression is achieved by sending chunk signatures instead of larger chunks of raw data over the network. When a DRE node receives a chunk signature sent by another DRE node, the recipient DRE node performs a lookup in its storage in order to restore original data corresponding to a given chunk signature. Since redundancy detection is done on a chunk by chunk basis, if there is a one-byte difference between two chunks, redundancy will not be detected. Accordingly, with smaller chunk sizes, more redundancies that can be detected and higher compression ratios can be achieved. However, small chunk sizes also mean that the DRE system needs to store a large number of chunks and to index a large number of chunk signatures for lookup. In some DRE systems, the amount of stored data could be as large as 500 GB, which can slow down network throughput, as lookup operations can be slow. Therefore, a DRE system faces a tradeoff. A large data storage is desirable in order to index a large number of data chunks and chunk signatures. However, with large data storage, the DRE system should somehow facilitate a fast lookup in order to detect redundancies to ensure that throughput is not unduly affected. Even with a large cache of data patterns in dynamic random access memory, not all of the data chunks and chunk signatures will fit into the cache.